package pers.vic.basics.leetcode;

import sun.misc.ObjectInputFilter;

/**
 * @description: 33. 搜索旋转排序数组
 * @author Vic.xu
 * @date: 2020/11/24 0024 16:55
 */
public class J0033_M_search {
    /*
    给你一个整数数组 nums ，和一个整数 target 。
    该整数数组原本是按升序排列，但输入时在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。
    请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

    要求算法时间复杂度必须是 O(logn)
     */

    /**
     * 原本是有序的 升序    要求算法时间复杂度必须是 O(logn)
     * 1. 旋转后必定存在0-mid-end 有一部分有序
     * 2. 有序的直接判断 start 和end
     * 3. 不在有序中 在无序中继续二分重复上述步骤
     *
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0;
        int r = len - 1;

        while (l <= r) {
            int mid = (r + l) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            //左边有序
            if (nums[mid] > nums[r]) {
                //判断在不在左边
                if (nums[l] <= target && nums[mid] >= target) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
                //右边有序
            } else {

                //判断在不在右边
                if (nums[r] >= target && nums[mid] <= target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        //4
        System.out.println(search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
        //-1
        System.out.println(search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3));
        //-1
        System.out.println(search(new int[]{3,1}, 0));
    }
}
